//
// Created by Administrator on 2021/4/15.
//

/*
给定二叉搜索树的根结点root，返回值位于范围 [low, high] 之间的所有结点的值的和。


示例 1：


输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32
示例 2：


输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23


提示：

树中节点数目在范围 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-of-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;


struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

class Solution {
public:
    int rangeSumBST1(TreeNode *root, int low, int high) {
        // 暴力  不用bst性质
        if (!root) return 0;
        int l = rangeSumBST1(root->left, low, high);
        int r = rangeSumBST1(root->right, low, high);
        return (root->val >= low and root->val <= high) ? (l + r + root->val) : (l + r);
    }  // AC 60%
    int rangeSumBST(TreeNode *root, int low, int high) {
        // 利用bst性质
        // 如果root.val < low 只在右边找
        // 如果root.val > high 只在左边找
        // 否则，两边都要找
        if (!root) return 0;
        if (root->val < low) {
            return rangeSumBST(root->right, low, high);
        } else if (root->val > high) {
            return rangeSumBST(root->left, low, high);
        } else {
            return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
        }
    }
};

int main() {
    auto t6 = TreeNode(18);
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(3);
    auto t3 = TreeNode(15, nullptr, &t6);
    auto t2 = TreeNode(5, &t4, &t5);
    auto t1 = TreeNode(10, &t2, &t3);

    Solution sol;
    cout << sol.rangeSumBST(&t1, 7, 15);
    return 0;
}